package com.salim.leetcode.$155;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: clevo
 * Date: 15-7-10
 * Time: 上午1:38
 * To change this template use File | Settings | File Templates.
 */
public class MinStackSector {


    Map<String,Integer> minMap = new HashMap<String,Integer>();
    List<Integer> stack = new ArrayList<Integer>();
    String sector = new String("Sector");
    Integer sectorSize = 250;

    MinStackSector(){
        minMap.put("totalSector",0);
        minMap.put("nowSector",0);
        minMap.put("Sector0",0);
    }

    public void push(int x) {
        //如果超出了数组长度 新建一个数组
        stack.add(x);
        if(stack.size()==1){
            minMap.put("Sector0",x);
        }
        int nowSector = stack.size()/sectorSize;
        String nowSectorStr = sector + nowSector;
        //如果push之后不属于当前分区 更新分区数 并计算老分区最小值
        if(nowSector > minMap.get("nowSector")){
            minMap.put("nowSector",nowSector);
            minMap.put(nowSectorStr,x);
        }else{
            if(minMap.containsKey(nowSectorStr)){
                if(x < minMap.get(nowSectorStr)){
                    minMap.put(nowSectorStr,x);
                }
            }
        }
    }

    public void pop() {
        int popTemp = stack.get(stack.size()-1);
        stack.remove(stack.size()-1);
        int oldSector = minMap.get("nowSector");
        //如果pop跨越了分区 nowSector-1 移除min
        if(stack.size() == (oldSector * sectorSize)-1){
            int beforeOldSector = oldSector -1;
            String beforeOldSectorStr = sector + beforeOldSector;
            minMap.put("nowSector",beforeOldSector);
            minMap.remove(beforeOldSectorStr);
        }else{
            String oldSectorStr = sector + oldSector;
            if(minMap.containsKey(oldSectorStr)){
                int oldMin = minMap.get(oldSectorStr );
                if(popTemp == oldMin){
                    minMap.remove(oldSectorStr);
                }
            }
        }
    }

    public int top() {
        return stack.get(stack.size()-1);
    }

    public int getMin() {
        int oldSector = minMap.get("nowSector");
        int min = stack.get(0);
        for(int i=0;i<oldSector+1;i++){
            String tempSectorStr = sector + i;
            //如果该分区已经算出最小值 直接比较 没有算出就算
            if(!minMap.containsKey(tempSectorStr)){
                int count = sectorSize;
                //如果是最新一个区
                if(i == oldSector){
                    count = stack.size() - oldSector*sectorSize;
                }
                for(int j=0;j<count;j++){
                    int subSectorTemp = stack.get(j+(i*sectorSize));
                    if(subSectorTemp < min){
                        min = subSectorTemp;
                    }
                }
            }else{
                if(minMap.get(tempSectorStr) < min){
                    min = minMap.get(tempSectorStr);
                }
            }
        }
        return min;
    }

    public static void main(String[] args){
        MinStackSector minStackSector = new MinStackSector();
        Random random=new Random();
        for(int i =0;i<200;i++){
            minStackSector.push(random.nextInt(500));
        }
        for(int i=0;i<101;i++){
            minStackSector.pop();
        }
        minStackSector.getMin();
        System.out.println(1);
        for(int j=0;j<200;j++){
            if(j%3 == 2){
                minStackSector.pop();
            }
            if(j%5 == 1){
                minStackSector.push(j);
            }
            if(j%10 == 1){
                minStackSector.getMin();
            }
        }
    }
}
